import java.util.ArrayList;
import java.util.Iterator;

/**
 * Created by asus on 2017/11/13.
 */
public class AMgroup<T> {
    private ArrayList<T> myList;

    private int[][] edges;
    private int NumEdges;
    private int room;
    public AMgroup (int n){
        edges = new int [n][n];
        myList = new ArrayList<>(n);
        NumEdges = 0;
        room = n;
    }

    public int getNumEdges(){
        return NumEdges;
    }
    public T GetData(int i){
        return myList.get(i);
    }
    public int getweight(int x,int y){
        return edges[x][y];
    }
    public void insertNode(T item){
        myList.add(item);
    }
    public void removeNode(T item){
        helpRemoveEdges(item);
        myList.remove(item);
    }
    public void helpRemoveEdges(T item){
        int position = myList.indexOf(item);
        int[][] Newedge = new int[room-1][room-1];
        for (int i=0;i<room;i++){
            if (i==position){
                continue;
            }
            if (i<position){
                for (int j=0;j<room;j++){
                    if (j==position)
                        continue;
                    if (j<position)
                        Newedge[i][j]=edges[i][j];
                    if (j>position)
                        Newedge[i][j-1]=edges[i][j];
                }
            }
            if (i>position){
                for (int j=0;j<room;j++){
                    if (j==position)
                        continue;
                    if (j<position)
                        Newedge[i-1][j]=edges[i][j];
                    if (j>position)
                        Newedge[i-1][j-1]=edges[i][j];
                }
            }
        }
        edges = Newedge;
    }
    public void insertEdge(int x,int y,int weight){
        edges[x][y]=weight;
        NumEdges++;
    }
    public void removeEdge(int x,int y){
        edges[x][y]=0;
        NumEdges--;
    }
    public int size(){
        return myList.size();
    }
    public boolean isEmpty(){
        if (myList.size()==0)
            return true;
        else return false;
    }
    public int getFirstNode(int i){
        for (int m=0;m<myList.size();m++){
            if (edges[i][m]>0)
                return m;
        }
        return -1;
    }
    public int getNextNode(int m,int n){
        for (int i=n+1;i<myList.size();i++){
            if (edges[m][i]>0){
                return i;
            }
        }
        return -1;
    }

    private void DFS(boolean[] isVisited,int i){
        System.out.print(GetData(i)+" ");
        isVisited[i]=true;
        int next = getFirstNode(i);
        while (next!=-1){
            if (!isVisited[next]){
                DFS(isVisited,next);
            }
            next = getNextNode(i,next);
        }
    }
    public Iterator<T> iteratorBFS(int startIndex){
        int currentVertex;
        LinkedQueue<Integer> traversalQueue = new LinkedQueue<>();
        ArrayIterator<T> iter = new ArrayIterator<>();
        if (!insexIsValid(startIndex))
            return iter;
        boolean[] visited = new boolean[myList.size()];
        for (int vertexIndex=0;vertexIndex<myList.size();vertexIndex++){
            visited[vertexIndex]= false;
        }
        traversalQueue.enqueue(startIndex);
        visited[startIndex] =  true;
        while (!traversalQueue.isEmpty()){
            currentVertex = traversalQueue.dequeue();
            iter.add(myList.get(currentVertex));
            for (int vertexIndex=0;vertexIndex<myList.size();vertexIndex++){
                if (edges[currentVertex][vertexIndex]>0&&!visited[vertexIndex]){
                    traversalQueue.enqueue(vertexIndex);
                    visited[vertexIndex] = true;
                }
            }
        }
        return iter;
    }
    public void BreadthFirstTraversal(int index){
        if (!insexIsValid(index)){
            throw new NumberFormatException("Wrong Number");
        }
        ArrayIterator<T> mIterator = (ArrayIterator<T>) iteratorBFS(index);
        while (mIterator.hasNext()){
            System.out.print(mIterator.next()+" ");
        }
    }
    public  boolean insexIsValid(int index){

        if (0<index&&index<myList.size()){
            return true;
        }
        else return false;
    }
    public Iterator<T> iteratorDFS(int startIndex){
        int currentVertex;
        LinkedStack<Integer> traversalStack = new LinkedStack<>();
        ArrayIterator<T> iter = new ArrayIterator<>();
        boolean[] visited = new boolean[myList.size()];
        boolean found;
        if (!insexIsValid(startIndex))
            return iter;
        for (int vertexIdx = 0;vertexIdx<myList.size();vertexIdx++){
            visited[vertexIdx] = false;
        }
        traversalStack.push(startIndex);
        iter.add(myList.get(startIndex));
        visited[startIndex] = true;
        while (!traversalStack.isEmpty()){
            currentVertex = traversalStack.peek();
            found = false;
            for (int vertexIdx = 0;vertexIdx<myList.size()&&!found;vertexIdx++)
                if (edges[currentVertex][vertexIdx]>0&&!visited[vertexIdx]){
                traversalStack.push(vertexIdx);
                iter.add(myList.get(vertexIdx));
                visited[vertexIdx] = true;
                found = true;
                }
                if (!found&&!traversalStack.isEmpty())
                    traversalStack.pop();
        }
        return iter;
    }
    public void DepthFirstTraversal(int index){
        if (!insexIsValid(index)){
            throw new NumberFormatException("Wrong number");
        }
        ArrayIterator<T> mIterator = (ArrayIterator<T>) iteratorDFS(index);
        while (mIterator.hasNext()){
            System.out.print(mIterator.next()+" ");
        }
    }
}
